package parens;

import java.util.HashSet;
import java.util.Set;


/**
 * 
 * @author Qu huanwen
 *
 */
public class Parens {

    /**
     * @param args
     */
    public static void main(String[] args) {
        Parens p = new Parens();
        print(p.allParens(0));
        print(p.allParens(1));
        print(p.allParens(2));
        print(p.allParens(3));
        print(p.allParens(4));
    }

    private static void print(String[] a) {
        for (String s : a)
            System.out.print(s + " ");
        System.out.println();
    }

    public String[] allParens(int n) {
        if (n == 0)
            return new String[] {};

        Set<String> set = new HashSet<String>();

        for (int i = 1; i <= n; i++) {
            String[] p = allParens(n - i);
            if (p.length == 0) {
                set.add(front(i, 0, ""));

            } else {
                for (String s : p) {
                    for(int j=1; j<=i*2; j++)
                        set.add(front(i, j, s));
                }
            }
        }
        return set.toArray(new String[] {});
    }

    private String front(int n, int p, String s) {
        StringBuffer b = new StringBuffer();
        int j = 0;
        for (int i = 0; i < n; i++, j++) {
            if (j == p)
                b.append(s);
            b.append("(");
        }
        for (int i = 0; i < n; i++, j++) {
            if (j == p)
                b.append(s);
            b.append(")");
        }
        if (j == p)
            b.append(s);
        return b.toString();

    }
}

